package com.asa.jihe.B;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.asa.jihe.utils.Line;
import com.asa.jihe.utils.Point;
import com.asa.jihe.utils.ToLeftTest;

/**
 * 凸包问题
 * 这里不搞那些花里胡哨的，直接实现我能实现的最优算法，效率低得算法也不实用
 * @author asa
 *
 */
public class Convex_Hull {
	
	
	public static void main(String[] args) {
		
		
		
		List<Point> pointList = initpointtolist();//注意这里不能用ArrayList，要用LinkedList
		
//		List<Point> jdList = method1(pointList);
//		System.out.println(jdList.size());//找到了两个极点
//
//		for (int i = 0; i < jdList.size(); i++) {
//			System.out.println(jdList.get(i).x+"        "+jdList.get(i).y);
//		}
		
		
		
		List<Point> jdList = method2(pointList);
		System.out.println("22222222222222222222222222222222222222222222222");
		
		for (int i = 0; i < jdList.size(); i++) {
			System.out.println(jdList.get(i).x+"        "+jdList.get(i).y);
		}
		
		
		
//		boolean leftTest = ToLeftTest.toLeftTest(pointList.get(0), pointList.get(1), pointList.get(2));
//		System.out.println(leftTest);
//		boolean leftTest2 = ToLeftTest.toLeftTest(pointList.get(0), pointList.get(1), pointList.get(2));
//		System.out.println(leftTest2);
//		boolean leftTest3 = ToLeftTest.toLeftTest(pointList.get(2),pointList.get(0), pointList.get(1));
//		System.out.println(leftTest3);
//		boolean leftTest4 = ToLeftTest.toLeftTest( pointList.get(1), pointList.get(2),pointList.get(0));
//		System.out.println(leftTest4);

	}


	/**
	 * 方案2，任意拿取两个点，假设这两个点是极点
	 * 然后将剩下的点一个又一个的点与这个集合进行判断
	 * 做完之后，发现是n的平方，我感到很欣慰呀。。。	但是我觉得算法的优化还是有不少空间的，但由于边际效应，你懂的！！！
	 * @param pointList
	 * @return
	 */
	public static List<Point> method2(List<Point> pointList) {
		List<Point> jdList = new LinkedList<>();//极点的集合
		
		Point lowest_leftmost = lowest_leftmost(pointList);//第一个点直接用极点，这样后面的计算步骤中就不需要在去判断排除第一个点了，对于数组来说要减轻很多的代码量
		lowest_leftmost.isselect=true;
		jdList.add(lowest_leftmost);
		
		
		for (int i = 0; i < pointList.size(); i++) {//这样我们就构成了一个三角形并且这个三角形点的次序是逆时针的
			
//			if (jdList.contains(pointList.get(i))) {
//				continue;
//			}
			if (pointList.get(i).isselect) {//不要使用contains方法，这个方法会循环遍历list增加算法复杂度
				continue;
			}
			
			
			
			
			if (jdList.size()<2) {
				pointList.get(i).isselect = true;
				jdList.add(pointList.get(i));
				continue;
			}
			
			if (ToLeftTest.toLeftTest(pointList.get(i), jdList.get(0), jdList.get(1))) {//构造出来三个点是有次序的逆时针的
				pointList.get(i).isselect=true;
				jdList.add(pointList.get(i));
				break;
			}

		}
		
		System.out.println("初始化的三个点"+jdList.size());
		for (int i = 0; i < jdList.size(); i++) {
			System.out.println(jdList.get(i).x+"        "+jdList.get(i).y);
		}
		
		for (int i = 0; i < pointList.size(); i++) {
			Point newpoint = pointList.get(i);
//			if (jdList.contains(newpoint)) {
//				continue;
//			}
			if (newpoint.isselect) {
				continue;
			}
			
			
			//判断是否是需要加入这个点,判断的条件就是
			//对现在所有的极边做toLeft
			//测试,如果通过了,就说明在现有的凸包里面,那就不用添加了
			//如果没有,我们需要找出哪些边有问题
			//这些边所在的点就是下个阶段我们需要去测试排除的
			
			boolean inout = false;
			
			List<Integer> testpoint = new ArrayList<>();//加入新的点，那么某些点就会被新加入的点所闭包，这样就要把这些可疑点找出来
			for (int j = 0; j < jdList.size(); j++) {
				int startindex = j;
				int endindex = 0;
				

				if (j<jdList.size()-1) {
					endindex = j+1;
				}
				Point spoint = jdList.get(startindex);
				Point epoint = jdList.get(endindex);
				
				
				
				
				boolean leftTest = ToLeftTest.toLeftTest(newpoint, spoint, epoint);
				
				if (!leftTest) {//如果这个是false就说明这个新的点不在
					if (!testpoint.contains(startindex)) {
						testpoint.add(startindex);
					}
					if (!testpoint.contains(endindex)) {
						testpoint.add(endindex);
					}
				}
				
			}
			
			
			
			//testpoint如果不是0，那么就说明这个新的点是需要我们排除一些无效点的
			if (testpoint.size()>2) {
				for (int j = testpoint.size()-2; j >=1 ; j--) {
					if (j==1) {
						newpoint.isselect = true;
						jdList.set(testpoint.get(j),newpoint);

					}else {
						jdList.remove(testpoint.get(j));

					}
				
				}
				
			}
			
			if (testpoint.size()==2) {
				newpoint.isselect=true;
				jdList.add(testpoint.get(0)+1, newpoint);
			}
			

			
			
		}
		
		
		
		for (int i = 0; i < pointList.size(); i++) {
			pointList.get(i).isselect = false;
		}
		
		
		
		return jdList;
	}
		












	/**
	 * 方案1，先找到两个极点，其实一个就够了，但我们没法只找一个				这种方法看上去是n平方的，但实际上应该是n立方，因为这里重置的i
	 * 然后根据已经找到的极点去遍历剩下来的点，一个一个将新的极点往极点几何里面添加
	 * 
	 * 存在bug懒得找了，别用
	 * @param pointList
	 * @return
	 */
	public static List<Point> method1(List<Point> pointList) {
		List<Point> jdList = new LinkedList<>();//极点的集合

		//先确定两个极点（这个必须要遍历所有的点，复杂度是n^3）
		//任意取三个点，假设这三个点就是极点，如果发现了更加合适的点作为极点，那么我们就移除不合适的，加入合适的点
		
		
		Point lowest_leftmost = lowest_leftmost(pointList);//第一个点直接用极点，这样后面的计算步骤中就不需要在去判断排除第一个点了，对于数组来说要减轻很多的代码量
		
		jdList.add(lowest_leftmost);
		
		System.out.println(jdList.size());//找到了两个极点

		for (int i = 0; i < jdList.size(); i++) {
			System.out.println(jdList.get(i).x+"        "+jdList.get(i).y);
		}
		
		//根据当前所有的极点去寻找下一个极点
		Point next = jdList.get(jdList.size()-1);

			
			
			movenext:for (int i = 0; i < pointList.size(); i++) {
				Point pointmove = pointList.get(i);
				if (jdList.contains(pointmove)) {
					continue;
				}
				
				for (int k = 0; k < pointList.size(); k++) {
	
					
						
					if (ToLeftTest.toLeftTest(pointList.get(k), next, pointmove)) {
						continue movenext;
					}
					
					if (k==pointList.size()-1) {
						pointmove.isselect=true;
						jdList.add(pointmove);
						next = pointmove;
						i=0;//这个骚操作，其实就是重置了movenext这个循环，这个算法的复杂度还是n^3
					}
				}
				
			}
		return jdList;
	}
	
	
	
	
	/**
	 * 这个是在1和2之后写的，暴力法
	 * 1和2存在bug
	 * 而事实证明，简单暴力是最稳定的	n的3次方
	 * 
	 * @param pointList
	 * @return
	 */
	public static List<Line> method0(List<Point> pointList) {
		System.out.println("计算凸包问题");
		for (int i = 0; i < pointList.size(); i++) {
			System.out.println(pointList.get(i));
		}
		
		List<Line> result = new LinkedList<>();
		
		for (int i = 0; i < pointList.size(); i++) {
			
			for (int j = 0; j < pointList.size(); j++) {
				
				if (i==j) {
					continue;
				}
				Point spoint = pointList.get(i);
				Point epoint = pointList.get(j);

				boolean tongce = ToLeftTest.tongce(pointList, spoint, epoint);
				
				if (tongce) {
					Line line = new Line();
					line.spoint = spoint;
					line.epoint = epoint;
					result.add(line);
				}
				
			}

		}
		
		for (int i = 0; i < result.size(); i++) {
			System.out.println(result.get(i));
		}
		
		
		
		
		
		
		
		
		return result;
	}

	
	
	
	
	
	
	
	
	
	
	
	/**
	 * 找出一个极点
	 * 这个方法比较好
	 * 根据坐标，找到y最小的点，如果有多个y最小的点，那么就取多个中x最小的点
	 * @return
	 */
	
	public static Point lowest_leftmost(List<Point> pointList) {
		Point minpoint = pointList.get(0);
		for (int i = 0; i < pointList.size(); i++) {
			
			if (minpoint.y>pointList.get(i).y) {
				minpoint = pointList.get(i);
				
			}else if (minpoint.y==pointList.get(i).y) {
				
				if (minpoint.x>pointList.get(i).x) {
					minpoint = pointList.get(i);
				}
				
			}
			
			
		}
		
		
		
		return minpoint;
		
	}
	
	
	
	
	
	
	
	
	
	
	
	
	private static Point[] copy(Point[] points) {
		Point[] points_ = new Point[points.length];
		for (int i = 0; i < points_.length; i++) {
			points_[i] = points[i];
		}
		
		return points_;
		
	}
	
	
	private static List<Point> initpointtolist() {
		Point[] points = new Point[10];
		
		points[0] = new Point();
		points[1] = new Point();
		points[2] = new Point();
		points[3] = new Point();
		points[4] = new Point();
		points[5] = new Point();
		points[6] = new Point();
		points[7] = new Point();
		points[8] = new Point();
		points[9] = new Point();
		
		//正方形的四个顶点
		points[2].x = 0;
		points[2].y = 0;
		points[7].x = 0;
		points[7].y = 2;
		points[4].x = 2;
		points[4].y = 2;
		points[6].x = 2;
		points[6].y = 0;
		
		
		points[0].x = 0.5;
		points[0].y = 1.5;
		points[3].x = 1.2;
		points[3].y = 1.2;
		points[5].x = 0.5;
		points[5].y = 1;
		points[1].x = 1;
		points[1].y = 0.5;
		points[8].x = 1;
		points[8].y = 1;
		
		points[9].x = 1;
		points[9].y = 4;
		
		
		
		List<Point> asList = new LinkedList<>();
		
		for (int i = 0; i < points.length; i++) {
			asList.add(points[i]);
		}
		
		
		return asList;
	}
	

	private static Point[] initpoint() {
		Point[] points = new Point[10];
		
		points[0] = new Point();
		points[1] = new Point();
		points[2] = new Point();
		points[3] = new Point();
		points[4] = new Point();
		points[5] = new Point();
		points[6] = new Point();
		points[7] = new Point();
		points[8] = new Point();
		points[9] = new Point();
		
		
		points[0].x = 0;
		points[0].y = 0;
		points[1].x = 0;
		points[1].y = 1;
		points[2].x = 0;
		points[2].y = 2;
		
		points[3].x = 1;
		points[3].y = 2;
		points[4].x = 2;
		points[4].y = 2;
		
		points[5].x = 2;
		points[5].y = 1;
		points[6].x = 2;
		points[6].y = 0;
		
		
		points[7].x = 1;
		points[7].y = 0;
		
		
		
		points[8].x = 1;
		points[8].y = 1;
		points[9].x = 1.5;
		points[9].y = 1.5;
		
		return points;
	}
	
	
	

}
